package com.zzz.dynamic;

import java.util.Arrays;

/**
 * Longest Increasing Subsequence
 *
 * @author zizan
 */
public class Lis {

    int[] elementLis;

    Lis(int num) {
        this.elementLis = new int[num];
    }

    public static void main(String[] args) {
        int[] array = {2, 5, 3, 6, 7, 4, 9};
        Lis instance = new Lis(array.length);


        System.out.println("-------------自顶向下求解---------------");
        instance.upLis(array);
        System.out.println(Arrays.toString(instance.elementLis));

        instance.elementLis = new int[array.length];

        System.out.println("-------------自下向上求解---------------");
        instance.downLis(array);
        System.out.println(Arrays.toString(instance.elementLis));
    }

    public void upLis(int[] array) {
        upLis(array, array.length - 1);
    }

    public int upLis(int[] array, int n) {


        if (elementLis[n] > 0) {
            System.out.println("    使用缓存  -----------" + (n + 1) + "--------------");
            return elementLis[n];
        }

        if (n == 0) {
            elementLis[0] = 1;
            return 1;
        }

        System.out.println("真实计算  -----------" + (n + 1) + "--------------");

        // 从n开始计算 需要获取第n-1 或者更小的位置的 子序列长度 就使用递归来求解
        // 每一元素 一定是 大于 0 的数，毕竟最差的情况是前面的元素都比 它大，那最大长度就只能是1了
        elementLis[n] = 1;
        // 遍历 比 n 小的元素，得到 lis(i) + 1 中 最大的值，如果没有比它小 那就只能是1了
        for (int i = n - 1; i >= 0; i--) {
            if (array[n] > array[i]) {
                elementLis[n] = Math.max(upLis(array, i) + 1, elementLis[n]);
            }
        }
        return elementLis[n];
    }

    // 自底向上求解，   可以看得出来，  不要简单太多, 无需递归
    // 因为先从底下求解，而求取每个元素的 最长长度 只和底下元素比较，是完全存在缓存中，直接获取即可
    // 而自顶向下要 递归去计算，无法知道该元素的值有没有被计算出来

    // 所以为什么 斐波那契数列 的自底向下 的实现那么简单，因为 它需要的缓存只有两个，f(n) 与 f(n-1)
    // 完全可以使用两个变量来存储
    // 最长递增子序列，需要和每一位的元素比较，只有对每个元素建立一个结果，所以需要一个数组来存储
    //
    // 缓存 elements 存储的是 对于 下标 n :  前n+1个 元素包含array(n) 的 递增子序列的长度
    // 因此我们要拿到前 n 个递增子序列最大长度，  需要从  1 。。。 n 所有的长度 选一个最大值

    // result(n) = max(elements[0  :  n-1])

    public void downLis(int[] array) {
        // 初始第一个元素，自然是1
        elementLis[0] = 1;

        for (int i = 1; i < array.length; i++) {

            // 最不济也是1
            elementLis[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (array[i] > array[j]) {
                    elementLis[i] = Math.max(elementLis[j] + 1, elementLis[i]);
                }
            }
        }
    }
}
